Abstract: Mobile devices with Geo positioning capabilities can send location-dependent queries to Location Based Services (LBS). To protect privacy of user, the location must not be disclosed to the server. Existing solutions utilize a trusted anonymizer between the users and the LBS. But the users are not protected from correlation attacks. Private Information Retrieval protocol is used to provide privacy to user location. This approach is secure, but it is expensive in terms of computational overhead. This paper specifies the use of Voronoi diagrams to solve the problem of secure outsourced kNN queries. Itemset with high profits are mined from the database. The itemset will be the query to the service provider. As the data owners do not have the infrastructure to process the query, so the dataset is outsourced to a cloud service provider. Secure voronoi cell enclosure evaluation is done to find the nearest neighbour.

Keywords: Location Based Service, Point of Interest, Anonymity, Private Information Retrieval, Voronoi Diagrams.